package com.example.task12vhourse;

import java.util.ArrayList;
import java.util.List;

public class KnightChess {
    private static int[][] moves = {{-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}};

    public static Cell findReachableCells(int[][] field, int startX, int startY, int N) {
        boolean[][] visited = new boolean[field.length][field[0].length];
        boolean[][] empty = new boolean[field.length][field[0].length];
        Cell res = dfs(field, startX, startY, N, visited, empty);
        return res;
    }


    private static void dfs(int[][] field, int x, int y, int movesLeft, List<Cell> reachableCells, boolean[][] visited,
                            int level) {
        if (movesLeft < 0 || x < 0 || y < 0 || x >= field.length || y >= field[0].length || visited[x][y]) {
            return;
        }
        visited[x][y] = true;
        if (field[x][y] == 0 && !check(x, y, reachableCells)) {
            Cell cell = new Cell(x, y);
            reachableCells.add(cell);
            for (int[] move : moves) {
                int newX = x + move[0];
                int newY = y + move[1];
                dfs(field, newX, newY, movesLeft - 1, reachableCells, visited, level + 1);
            }
        }
        visited[x][y] = false;
    }

    private static Cell dfs(int[][] field, int x, int y, int movesLeft, boolean[][] visited, boolean[][] empty) {
        if (movesLeft < 0 || x < 0 || y < 0 || x >= field.length || y >= field[0].length || visited[x][y]) {
            return null;
        }
        Cell parent = null;
        visited[x][y] = true;
        if (field[x][y] == 0 && !empty[x][y]) {
            parent = new Cell(x, y);
            parent.childs = new ArrayList<>();
            empty[x][y] = true;
            for (int[] move : moves) {
                int newX = x + move[0];
                int newY = y + move[1];
                Cell t = dfs(field, newX, newY, movesLeft - 1, visited, empty);
                if (t != null) {
                    parent.childs.add(t);
                }
            }
        }
        visited[x][y] = false;
        return parent;
    }

    private static boolean check(int x, int y, List<Cell> reachable) {
        for (var i : reachable) {
            if (i.x == x && i.y == y) {
                return true;
            }
        }
        return false;
    }

    static class Cell {
        int x;
        int y;
        List<Cell> childs;

        Cell(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}